package com.algoruthm6;

import java.util.Arrays;

public class QuickSort {
    public static  void sort(int[] array,int start,int end){
      if(start>=end){
          return;
      }
      int r = partion(array,start,end);
      sort(array,start,r-1);
      sort(array,r+1,end);

    }
    public static  int partion(int[] array,int s,int e){
        int pivot = array[e];
        int i=s,j=e;
        while(i!=j){
            if(array[i]>=pivot && array[j]<=pivot){
                Utils.swap(array,i,j);
            }
            if(array[i]<pivot){
                i++;
            }
            if(array[j]>pivot){
                j--;
            }
        }
        if(array[i]>pivot)
        Utils.swap(array,i,e);
        System.out.println("pivot值:"+pivot+"-->s="+s+";e="+e+"-->array:"+ Arrays.toString(array));
        return i;
    }

    public static void main(String[] args){
        int[] array = new int[]{4,3,5,8,9,7,10,6,1,2};
        System.out.println("array:"+ Arrays.toString(array));
        sort(array,0,array.length-1);
        System.out.println("sorted array:"+ Arrays.toString(array));
    }
}
